//
// Created by 郑楚彬 on 2018/4/12.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define Max 100

/**
 * 二叉链表节点类型定义
 */
typedef struct BiTNode{
    char data;
    BiTNode *lchild;
    BiTNode *rchild;
    // 习题5
    BiTNode *parent;
}BiTNode;

/**
 * 初始化一个二叉树的节点(按序号建)
 *
 * @param root 双亲节点
 * @param elements 字符数组
 * @param n    节点数
 */
void init(BiTNode *&root, char* &elements){
    char c = *elements;
    if(c == '\0'){
        return;
    }

    if('#' == c){
        root = NULL;
        elements++;
        return;
    }else{
        root = (BiTNode *) malloc(sizeof(BiTNode *));
        root->data = c;

        cout << *elements << endl;
        elements++;
        init(root->lchild, elements);
        init(root->rchild, elements);
    }
}

/**
 * 先序遍历
 */
/*
 * 递归形式
 * @param bt
 */
void preorder(BiTNode *&bt){
    if(bt == NULL){
        return;
    }
    cout << bt->data << ' ';
    preorder(bt->lchild);
    preorder(bt->rchild);
}

/*
 * 非递归形式
 * @param bt
 */
void preorderNonRecursion(BiTNode *&bt){
    if(bt != NULL){
        // 定义栈
        int top = -1;
        BiTNode* stack[Max];

        // 根节点入栈
        stack[++top] = bt;
        BiTNode *q=NULL;

        while(top != -1){
            q = stack[top--];
            cout << q->data << '\t';

            // 先入栈后出，与正常遍历顺序相反
            if(q->rchild != NULL){
                stack[++top] = q->rchild;
            }

            if(q->lchild != NULL){
                stack[++top] = q->lchild;
            }
        }
    }
}

/**
 * 中序遍历
 * @param bt
 */
void inorder(BiTNode *&bt){
    if(bt == NULL){
        return;
    }
    inorder(bt->lchild);
    cout << bt->data << ' ';
    inorder(bt->rchild);
}

/*
 * 非递归形式
 * @param bt
 */
void inorderNonRecursion(BiTNode *&bt){
    if(bt != NULL){
        BiTNode* stack[Max];
        int top = -1;
        BiTNode* p=bt;

        // 有可能出现栈空但遍历还没有结束的情况
        while(top!=-1 || p!=NULL){

            // 左子树不为空，则入栈
            while(p!=NULL){
                stack[++top] = p;
                p = p->lchild;
            }

            // 栈不为空出栈
            if(top != -1){
                p = stack[top--];
                cout << p->data << '\t';
                p = p->rchild;
            }
        }
    }
}


/**
 * 后序遍历
 * @param bt
 */
void postorder(BiTNode *&bt){
    if(bt == NULL){
        return;
    }
    inorder(bt->lchild);
    inorder(bt->rchild);
    cout << bt->data << ' ';
}


/*
 * 非递归后序遍历
 *
 * @param bt
 */
vector<int> postOrder(TreeNode *root)
{
    vector<int> res;
    if(root == NULL) return res;

    TreeNode *p = root;
    stack<TreeNode *> sta;
    TreeNode *last = root;
    sta.push(p);
    while (!sta.empty())
    {
        p = sta.top();
        if( (p->left == NULL && p->right == NULL) || (p->right == NULL && last == p->left) || (last == p->right) )
        {
            res.push_back(p->val);
            last = p;
            sta.pop();
        }
        else 
        {
            if(p->right)
                sta.push(p->right);
            if(p->left)
                sta.push(p->left);
        }

    }


    return res;
}


/*
 * 逆序后序遍历序列 = 先序遍历过程中树的左右子树遍历顺序交换所得的结果
 *
 * @param bt
 */
void postorderNonRecursion(BiTNode *&bt){
    if(bt != NULL){
        BiTNode* stack1[Max];
        int top1 = -1;

        BiTNode* stack2[Max];
        int top2 = -1;

        BiTNode* p=NULL;
        stack1[++top1] = bt;
        while(top1 != -1){
            p = stack1[top1--];
            stack2[++top2] = p;

            // 与先序遍历相反
            if(p->lchild != NULL){
                stack1[++top1] = p->lchild;
            }

            if(p->rchild != NULL){
                stack1[++top1] = p->rchild;
            }
        }

        // 输出最终结果
        while(top2 != -1){
            p = stack2[top2--];
            cout << p->data << '\t';
        }
    }
}

/*
 * 层次遍历
 */
void level(BiTNode *p){
    if(p == NULL){
        return;
    }
    // 循环队列
    BiTNode* queue[Max];
    int front=0, rear=0;
    BiTNode* q;

    // 根节点进队
    rear = (rear+1)%Max;
    queue[rear] = p;

    // 队列不空时循环
    while(front != rear){
        // 出队
        front = (front + 1) % Max;
        q = queue[front];
        cout << q->data << '\t';

        if(p->lchild != NULL){
            rear = (rear+1)%Max;
            queue[rear] = p->lchild;
        }

        if(p->rchild != NULL){
            rear = (rear+1)%Max;
            queue[rear] = p->rchild;
        }
    }
}

/**
 * 求一棵二叉树的深度，二叉树以二叉链表为存储方式
 *
 * 思路:
 *      树的深度= max(LD, RD) + 1
 *   即 左子树与右子树深度的最大值+1
 * *@param bt
 */
int getDeepth(BiTNode *bt){
    int LD, RD;
    if(bt == NULL){
        return 0;
    }else{
        LD = getDeepth(bt->lchild);
        RD = getDeepth(bt->rchild);
        return (LD>RD?LD:RD) + 1;
    }
}

/**
 * 查找值域等于key的节点
 *
 * @param bt   二叉树
 * @param q    待求节点
 * @param key  匹配值
 */
void search(BiTNode *bt, BiTNode *&q, char key){
    if(bt == NULL){
        return;
    }
    // 如果值相等，则q指向值域等于key的节点
    if(bt->data == key) {
        q = bt;
    }else{
        // 否则分别到左右子树上查找
        search(bt->lchild, q, key);
        search(bt->rchild, q, key);
    }
}


/**
 * 两棵二叉排序树合并
 *
 */
void Insert(BinTree *T,int key)
{
    if(!(*T))
    {
        (*T) = (BinTree)malloc(sizeof(BinNode));
        (*T)->data = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return;
    }
    if(key == (*T)->data )
        return;
    if(key > (*T)->data )
        Insert( &((*T)->rchild), key );
    else
        Insert( &((*T)->lchild), key );
}
 
void InsertBST(BinTree T1,BinTree T2)
{
    if(T2)
    {
        InsertBST(T1,T2->lchild);
        Insert(&T1,T2->data);
        InsertBST(T1,T2->rchild);
    }
}

/*
 * 5. 假设二叉树采用二叉链表存储结构存储，设计一个算法，求出该二叉树的宽度
 *    (具有节点数最多的那一层上的节点个数)。
 */
typedef struct{
    BiTNode *p;
    int lno;
}St;

int maxNode(BiTNode *p){
    St queue[Max];
    int front=0, rear=0, LNO=0;
    BiTNode *q;

    if(p != NULL){
        // 第一个节点进队
        rear++;
        queue[rear].p = p;     // 根节点进队
        queue[rear].lno = 1;   // 根节点层数为1

        while(front != rear){
            // 节点出队时保存节点所在的层数
            front++;
            LNO = queue[front].lno;
            q = queue[front].p;

            if(q->lchild != NULL){
                // 左子树不为空，行数+1，并进队
                rear++;
                queue[rear].p = q->lchild;
                queue[rear].lno = LNO+1;
            }

            if(q->rchild != NULL){
                // 右子树不为空，行数+1，并进队
                rear++;
                queue[rear].p = q->rchild;
                queue[rear].lno = LNO+1;
            }
        }

        // 保留最大节点数
        int max=0;
        int i,j,n;

        // 按层数遍历队列
        for(j=1; j<=LNO; j++){
            n = 0;
            for(i=1; i<=rear; i++){
                // 统计每层节点数
                if(queue[i].lno == j){
                    n++;
                }
                if(n > max){
                    max = n;
                }
            }
        }
        return max;
    }else{
        return 0; // 空树直接返回0
    }
}

/*
 * 2. 已知二叉树的节点在先序遍历下的序列存储在一维数组 pre[l1,...,r1] 中，在中序遍历下的
 *    序列存储在一维数组 in[l2,...,r2] 中(其中l1，r2与l2，r2指示了数组中元素(类型为char)
 *    存储的下标范围)，假定二叉树中节点数据值互不相同。试写出 pre[l1,...,r1] 和 in[l2,...,r2]
 *    构造二叉树的算法。
 *  (1) 给出基本设计思想
 *  (2) 根据设计思想，采用 c 或 c++ 语言描述算法，关键之处给出注释
 *  (3) 分析本算法的时间复杂度
 */
BiTNode * constructBiTree(char pre[], char in[], int l1, int r1,  int l2, int r2){
    if(l1 > r1){
       return NULL;
    }
    int i,j;
    BiTNode *root;
    // 将当前子树根节点赋值给新申请的节点
    for(i=l2; i<=r2; i++){
        if(pre[l1]==in[i]){
            root = (BiTNode *) malloc(sizeof(BiTNode *));
            root->data = pre[l1];
            root->lchild = NULL;
            root->rchild = NULL;
            break;
        }
    }
    // 确定左子树在先序序列和中序序列中的位置
    root->lchild = constructBiTree(pre, in, l1+1, l1+i-l2, l2, i-1);
    // 确定右子树在先序序列和中序序列中的位置
    root->rchild = constructBiTree(pre, in, l1+i-l2+1, r1, i+1, r2);
    return root;
}

/*
 * 3. 假设二叉树采用二叉链存储结构，设计一个算法，利用节点的右孩子指针 rchild 将一棵二叉树
 *   的叶子节点按照从左往右的顺序串成一个单链表(在题目中定义两个指针，head与tail，其中，head
 *   指向第一个叶子节点，head 初值为 NULL，tail 指向最后一个叶子节点)
 */
void link(BiTNode *root, BiTNode *&head, BiTNode *&tail){
    if(root!=NULL){
        if(root->lchild==NULL && root->rchild==NULL){
            if(head == NULL){
                head = root;
                tail = root;
            }else{
                tail->rchild = root;
                tail = root;
            }
        }
        link(root->lchild, head, tail);
        link(root->rchild, head, tail);
    }
}

/*
 * 6. 假设满二叉树 b 先序遍历序列已经存在数组中，长度为 n ，设计一个算法将其转换为后序遍历序列
 */
void change(char pre[], int l1, int r1, char post[], int l2, int r2){
    if(l1<=r1){
        // 将根放于末尾
        post[r2] = pre[l1];

        // 改变左子树部分
        change(pre, l1+1, (l1+1+r1)/2, post, l2, (l2+r2-1)/2);
        // 改变左子树部分
        change(pre, (l1+1+r1)/2+1, r1, post, (l2+r2-1)/2+1, r2-1);
    }
}

/*
 * 7. 假设二叉树采用二叉链存储结构，设计一个算法，求二叉树 b 中值为 x 的节点的层号。
 */
int LNO=1;
void findX(BiTNode *p, char x){
    if(p!=NULL){
        if(p->data == x){
            cout << x << ", 层号:"<<LNO<< endl;
        }
        // 进入左右子树，层号+1
        ++LNO;
        findX(p->lchild, x);
        findX(p->rchild, x);
        --LNO;
        // 返回上一层，层号-1
    }
}

/*
 * 1. 假设二叉树采用二叉链存储结构，设计一个算法，输出根节点到每个叶子节点的路径。
 */
int top=-1;
int i=0;
BiTNode* stack[100];
void printAllLeafPath(BiTNode *p){
    if(p!=NULL){
        stack[++top] = p;
        // 如果是叶子节点，则打印路径
        if(p->lchild==NULL && p->rchild==NULL){
            for(i=0; i<=top; i++){
                cout<<stack[i]->data<<" -> ";
            }
            cout<<"NULL"<<endl;
        }
        printAllLeafPath(p->lchild);
        printAllLeafPath(p->rchild);
        top--;
    }
}
